#include "set.h"

// Could have been put directly into the Set constructor, but when talking about
// disjoint sets, the commonly used operations are make, find and union, so we
// stick to that
Set *makeSet()
{
	Set *newNode = new Set();
	newNode->parent = newNode;
	return newNode;
}

Set *findParent(Set *node)
{
	if (node->parent == node)
		return node;
	else
	{
		node->parent = findParent(node->parent);
		return node->parent;
	}
}

void unionSets(Set *n1, Set *n2)
{
	Set *xRoot = findParent(n1);
	Set *yRoot = findParent(n2);
	if (xRoot == yRoot)
		return;

	if (xRoot->rank < yRoot->rank)
		xRoot->parent = yRoot;
	else if (xRoot->rank > yRoot->rank)
		yRoot->parent = xRoot;
	else
	{
		yRoot->parent = xRoot;
		(xRoot->rank)++;
	}
}
